package leetcode101.greedy_strategy;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code7
 * @Description You are given an array prices where prices[i] is the price of a given stock on the ith day.
 *
 * Find the maximum profit you can achieve.
 * You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
 *
 * Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
 *
 * Example 1:
 *
 * Input: prices = [7,1,5,3,6,4]
 * Output: 7
 * Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
 * Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
 * Example 2:
 *
 * Input: prices = [1,2,3,4,5]
 * Output: 4
 * Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
 * Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
 * Example 3:
 *
 * Input: prices = [7,6,4,3,1]
 * Output: 0
 * Explanation: In this case, no transaction is done, i.e., max profit = 0.
 *
 *
 * Constraints:
 * 1 <= prices.length <= 3 * 104
 * 0 <= prices[i] <= 104
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-25 19:22
 */
public class Code7 {

    public static void main(String[] args) {

    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
}

/*
定义状态dp[i][0]表示第i填交易完后手里没有股票的最大利润，dp[i][1]表示第i天交易完后手里有一只股票的最大利润(i从0开始)
考虑dp[i][0]的转移方程，如果这一天交易完后手里没有股票，那么可能转移状态为前一天也没有股票，即dp[i - 1][0]
或者说前一天结束的时候手里持有一只股票，即dp[i - 1][1]这时候我们需要将其卖出，并获得prices[i]的收益，因此为了收益最大化我们列出如下
转移方程：
dp[i][0] = max{dp[i - 1][0], dp[i - 1][1] + prices[i]}

再来考虑dp[i][1]按照同样的方式考虑转移状态，那么可能的转移状态为前一天已经持有一只股票，即dp[i - 1][1]，或者前一天结束时还没有股票
即dp[i - 1][0]这时候我们要将其买入，并减少prices[i]的收益，因此我们列出如下转移方程：

 */